<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>Java基础2-HashMap底层原理 | Hexo</title>
  <meta name="keywords" content="">
  <meta name="description" content="Java基础2-HashMap底层原理 | Hexo">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick">
<meta property="og:type" content="article">
<meta property="og:title" content="Hello World">
<meta property="og:url" content="http://yoursite.com/2020/07/27/hello-world/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2020-07-27T05:17:47.002Z">
<meta property="article:modified_time" content="2020-07-27T05:17:47.002Z">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.1.0" rel="stylesheet">

<link href="/css/hl_theme/atom-light.css?v=1.1.0" rel="stylesheet">

<link href="//cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" rel="stylesheet">

<script src="//cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="/js/titleTip.js?v=1.1.0" ></script>

<script src="//cdn.jsdelivr.net/npm/highlightjs@9.16.2/highlight.pack.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>



<script src="//cdn.jsdelivr.net/npm/jquery.cookie@1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.1.0" ></script>

<meta name="generator" content="Hexo 4.2.1"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="">
  <input class="theme_blog_path" value="">
  <input id="theme_shortcut" value="true" />
</div>


<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>John Doe</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-rss"></use>
                </svg>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/yelog" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-github"></use>
                </svg>
            
        </a>
        
    
        
        <a title="facebook" href="https://www.facebook.com/faker.tops" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-facebook"></use>
                </svg>
            
        </a>
        
    
        
    
        
    
        
        <a title="instagram" href="https://www.facebook.com/faker.tops" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-instagram"></use>
                </svg>
            
        </a>
        
    
        
        <a title="reddit" href="https://www.reddit.com/user/yelog/" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-reddit"></use>
                </svg>
            
        </a>
        
    
        
        <a title="weibo" href="http://weibo.com/u/2307534817" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-weibo"></use>
                </svg>
            
        </a>
        
    
        
        <a title="jianshu" href="https://www.jianshu.com/u/ff56736de7cf" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-jianshu"></use>
                </svg>
            
        </a>
        
    
        
        <a title="zhihu" href="https://www.zhihu.com/people/jaytp/activities" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-zhihu"></use>
                </svg>
            
        </a>
        
    
        
    
        
        <a title="oschina" href="https://my.oschina.net/yelog" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-oschina"></use>
                </svg>
            
        </a>
        
    
        
    
        
        <a title="email" href="mailto:jaytp@qq.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=872336115&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
        
        <a title="kugou" href="https://www.kugou.com/" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-kugou"></use>
                </svg>
            
        </a>
        
    
        
        <a title="neteasemusic" href="https://music.163.com/#/user/home?id=88151013" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-neteasemusic"></use>
                </svg>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active" data-rel="All">All<small>(10)</small></div></li>
    
        
            
            <li><div data-rel="后端">后端<small>(3)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Java基础">Java基础<small>(4)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">About</a><a style="width: 50%"  class="friends">Friends</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="10">

<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        Links
        <i class="iconfont icon-left"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <div class="right-top">
        <div id="default-panel">
            <i class="iconfont icon-search" data-title="搜索 快捷键 i"></i>
            <div class="right-title">All</div>
            <i class="iconfont icon-file-tree" data-title="切换到大纲视图 快捷键 w"></i>
        </div>
        <div id="search-panel">
            <i class="iconfont icon-left" data-title="返回"></i>
            <input id="local-search-input" />
            <label class="border-line" for="input"></label>
            <i class="iconfont icon-case-sensitive" data-title="大小写敏感"></i>
            <i class="iconfont icon-tag" data-title="标签"></i>
        </div>
        <div id="outline-panel" style="display: none">
            <div class="right-title">大纲</div>
            <i class="iconfont icon-list" data-title="切换到文章列表"></i>
        </div>
    </div>

    <div class="tags-list">
    <input id="tag-search" />
    <div class="tag-wrapper">
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>Git</a>
            </li>
        
    </div>

</div>

    
    <nav id="title-list-nav">
        
        <a  class="All "
           href="/2020/07/27/%E5%BE%AE%E6%9C%8D%E5%8A%A1%E9%98%B6%E6%AE%B5/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="微服务阶段">微服务阶段</span>
            <span class="post-date" title="2020-07-27 14:31:06">2020/07/27</span>
        </a>
        
        <a  class="All "
           href="/2020/07/27/hello-world/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Hello World">Hello World</span>
            <span class="post-date" title="2020-07-27 13:17:47">2020/07/27</span>
        </a>
        
        <a  class="All "
           href="/2020/07/23/Java%E5%9F%BA%E7%A1%805/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Java基础5-">Java基础5-</span>
            <span class="post-date" title="2020-07-23 23:51:18">2020/07/23</span>
        </a>
        
        <a  class="All Java基础 "
           href="/2020/07/21/Java%E5%9F%BA%E7%A1%804-%E8%AF%A6%E8%A7%A3-ThreadPoolExecutor-%E7%9A%84%E5%8F%82%E6%95%B0%E5%90%AB%E4%B9%89%E5%8F%8A%E6%BA%90%E7%A0%81%E6%89%A7%E8%A1%8C%E6%B5%81%E7%A8%8B/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="java基础4-详解 ThreadPoolExecutor 的参数含义及源码执行流程">java基础4-详解 ThreadPoolExecutor 的参数含义及源码执行流程</span>
            <span class="post-date" title="2020-07-21 21:53:39">2020/07/21</span>
        </a>
        
        <a  class="All Java基础 "
           href="/2020/07/20/Java%E5%9F%BA%E7%A1%803-%E7%BA%BF%E7%A8%8B%E7%9A%84%E7%8A%B6%E6%80%81%E6%9C%89%E5%93%AA%E4%BA%9B/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Java基础3-线程的状态有哪些">Java基础3-线程的状态有哪些</span>
            <span class="post-date" title="2020-07-20 10:21:12">2020/07/20</span>
        </a>
        
        <a  class="All Java基础 "
           href="/2020/07/17/Java%E5%9F%BA%E7%A1%802-HashMap%E5%BA%95%E5%B1%82%E5%8E%9F%E7%90%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Java基础2-HashMap底层原理">Java基础2-HashMap底层原理</span>
            <span class="post-date" title="2020-07-17 13:02:46">2020/07/17</span>
        </a>
        
        <a  class="All Java基础 "
           href="/2020/07/13/Java%E5%9F%BA%E7%A1%801-Spring%E7%89%B9%E7%82%B9%E6%98%AF%E4%BB%80%E4%B9%88/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Java基础1-Spring特点是什么">Java基础1-Spring特点是什么</span>
            <span class="post-date" title="2020-07-13 17:24:53">2020/07/13</span>
        </a>
        
        <a  class="All 后端 "
           href="/2020/07/09/%E4%BD%BF%E7%94%A8SSH%E5%AF%86%E9%92%A5%E8%BF%9E%E6%8E%A5Github/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="使用SSH密钥连接Github">使用SSH密钥连接Github</span>
            <span class="post-date" title="2020-07-09 18:13:36">2020/07/09</span>
        </a>
        
        <a  class="All 后端 "
           href="/2020/07/09/%E6%89%8B%E6%8A%8A%E6%89%8B%E6%95%99%E4%BD%A0%E4%BB%8E0%E5%BC%80%E5%A7%8B%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="手把手教你从0开始搭建个人博客">手把手教你从0开始搭建个人博客</span>
            <span class="post-date" title="2020-07-09 17:27:06">2020/07/09</span>
        </a>
        
        <a  class="All 后端 "
           href="/2020/07/08/Git%E5%AE%89%E8%A3%85/"
           data-tag="Git"
           data-author="" >
            <span class="post-title" title="Git安装">Git安装</span>
            <span class="post-date" title="2020-07-08 13:04:43">2020/07/08</span>
        </a>
        
        <div id="no-item-tips">

        </div>
    </nav>
    <div id="outline-list">
    </div>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div id="post">
    <div class="pjax">
        <article id="post-Java基础2-HashMap底层原理" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">Java基础2-HashMap底层原理</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            <i class="iconfont icon-category"></i>
            
            <a  data-rel="Java基础">Java基础</a>
            
        </span>
        
        
    </div>
    <div class="article-meta">
        
            Created At : <time class="date" title='Updated At: 2020-07-21 21:39:58'>2020-07-17 13:02</time>
        
    </div>
    <div class="article-meta">
        
        
        <span id="busuanzi_container_page_pv">
            Views 👀 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#一、HashMap-底层是如何实现的"><span class="toc-text">一、HashMap 底层是如何实现的</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#在-JDK-1-8-中它都做了哪些优化"><span class="toc-text">在 JDK 1.8 中它都做了哪些优化</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-HashMap-源码分析"><span class="toc-text">1.HashMap 源码分析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-HashMap-死循环分析"><span class="toc-text">2.HashMap 死循环分析</span></a></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-3 i,
    .toc-level-3 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="一、HashMap-底层是如何实现的"><a href="#一、HashMap-底层是如何实现的" class="headerlink" title="一、HashMap 底层是如何实现的"></a>一、HashMap 底层是如何实现的</h1><hr>
<p><strong>HashMap 是使用频率最高的类型之一，同时也是面试经常被问到的问题之一，这是因为 HashMap 的知识点有很多，同时它又属于 Java 基础知识的一部分，因此在面试中经常被问到。</strong></p>
<blockquote>
<p>在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的，JDK 1.8 之后新增了红黑树的组成结构，当链表大于 8 并且容量大于 64 时，链表结构会转换成红黑树结构，它的组成结构如下图所示：</p>
</blockquote>
<p><img src="https://s1.ax1x.com/2020/07/20/Uf7mrT.md.png" alt=""></p>
<blockquote>
<p>数组中的元素我们称之为哈希桶，它的定义如下：</p>
</blockquote>
<pre class="brush:java">
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
</pre>

<blockquote>
<p>可以看出每个哈希桶中包含了四个字段：hash、key、value、next，其中 next 表示链表的下一个节点。</p>
</blockquote>
<hr>
<blockquote>
<p>JDK 1.8 之所以添加红黑树是因为一旦链表过长，会严重影响 HashMap 的性能，而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长时操作比较慢的问题。</p>
</blockquote>
<p><strong>考点分析</strong></p>
<hr>
<p>上面大体介绍了 HashMap 的组成结构，但面试官想要知道的远远不止这些，和 HashMap 相关的面试题还有以下几个：</p>
<blockquote>
<p>JDK 1.8 HashMap 扩容时做了哪些优化？</p>
</blockquote>
<blockquote>
<p>加载因子为什么是 0.75？</p>
</blockquote>
<blockquote>
<p>当有哈希冲突时，HashMap 是如何查找并确认元素的？</p>
</blockquote>
<ul>
<li><p>HashMap 源码中有哪些重要的方法？</p>
</li>
<li><p>HashMap 是如何导致死循环的？</p>
</li>
</ul>
<hr>
<h1 id="在-JDK-1-8-中它都做了哪些优化"><a href="#在-JDK-1-8-中它都做了哪些优化" class="headerlink" title="在 JDK 1.8 中它都做了哪些优化"></a>在 JDK 1.8 中它都做了哪些优化</h1><hr>
<p><strong>知识扩展</strong></p>
<hr>
<h2 id="1-HashMap-源码分析"><a href="#1-HashMap-源码分析" class="headerlink" title="1.HashMap 源码分析"></a><strong>1.HashMap 源码分析</strong></h2><hr>
<blockquote>
<p>声明：本系列课程在未做特殊说明的情况下，都是以目前主流的 JDK 版本 1.8 为例来进行源码分析的。</p>
</blockquote>
<p><strong>HashMap 源码中包含了以下几个属性：</strong></p>
<pre class="brush:java">
// HashMap 初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// HashMap 最大长度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824

// 默认的加载因子 (扩容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 当链表长度大于此值且容量大于 64 时
static final int TREEIFY_THRESHOLD = 8;

// 转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表结构
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树容量
static final int MIN_TREEIFY_CAPACITY =
什么是加载因子？加载因子为什么是 0.75？
</pre>

<blockquote>
<p>加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，假如加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。</p>
</blockquote>
<blockquote>
<p>那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢？</p>
</blockquote>
<blockquote>
<p>这其实是出于容量和性能之间平衡的结果：</p>
</blockquote>
<ul>
<li>当加载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生 Hash 冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；而当加载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。</li>
</ul>
<p><strong>所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。</strong></p>
<hr>
<p><strong>HashMap 源码中三个重要方法：查询、新增和数据扩容。</strong></p>
<p>先来看查询源码：</p>
<pre class="brush:java">
public V get(Object key) {
    Node<K,V> e;
    // 对 key 进行哈希操作
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 非空判断
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个元素是否是要查询的元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 下一个节点非空判断
        if ((e = first.next) != null) {
            // 如果第一节点是树结构，则使用 getTreeNode 直接获取相应的数据
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 非树结构，循环节点判断
                // hash 相等并且 key 相同，则返回此节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
</pre>

<p>从以上源码可以看出，当哈希冲突时我们需要通过判断 key 值是否相等，才能确认此元素是不是我们想要的元素。</p>
<hr>
<p><strong>HashMap 第二个重要方法：新增方法，源码如下：</strong></p>
<pre class="brush:java">
public V put(K key, V value) {
    // 对 key 进行哈希操作
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 哈希表为空则创建表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根据 key 的哈希值计算出要插入的数组索引 i
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果 table[i] 等于 null，则直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果 key 已经存在了，直接覆盖 value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果 key 不存在，判断是否为红黑树
        else if (p instanceof TreeNode)
            // 红黑树直接插入键值对
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 为链表结构，循环准备插入
            for (int binCount = 0; ; ++binCount) {
                // 下一个元素为空时
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //  key 已经存在直接覆盖 value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过最大容量，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
</pre>

<hr>
<p><strong>新增方法的执行流程，如下图所示：</strong></p>
<p><img src="https://s1.ax1x.com/2020/07/20/Uf7eMV.png" alt=""></p>
<blockquote>
<p>HashMap 第三个重要的方法是扩容方法，源码如下：</p>
</blockquote>
<pre class="brush:java">
final Node<K,V>[] resize() {
    // 扩容前的数组
    Node<K,V>[] oldTab = table;
    // 扩容前的数组的大小和阈值
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    // 预定义新数组的大小和阈值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不再扩容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 扩大容量为当前容量的两倍，但不能超过 MAXIMUM_CAPACITY
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 当前数组没有数据，使用初始化的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 如果初始化的值为 0，则使用默认的初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的容量等于 0
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; 
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 开始扩容，将新的容量赋值给 table
    table = newTab;
    // 原数据不为空，将原数据复制到新 table 中
    if (oldTab != null) {
        // 根据容量循环数组，复制非空元素到新 table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果链表只有一个，则进行直接赋值
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 红黑树相关的操作
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 链表复制，JDK 1.8 扩容优化部分
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将原索引放到哈希桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 将原索引 + oldCap 放到哈希桶中
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
</pre>

<blockquote>
<p>从以上源码可以看出，JDK 1.8 在扩容时并没有像 JDK 1.7 那样，重新计算每个元素的哈希值，而是通过高位运算（e.hash &amp; oldCap）来确定元素是否需要移动，比如 key1 的信息如下：</p>
</blockquote>
<pre class="brush:java">
key1.hash = 10 0000 1010

oldCap = 16 0001 0000
</pre>

<blockquote>
<p>使用 e.hash &amp; oldCap 得到的结果，高一位为 0，当结果为 0 时表示元素在扩容时位置不会发生任何变化，而 key 2 信息如下：</p>
</blockquote>
<pre class="brush:java">
key2.hash = 10 0001 0001

oldCap = 16 0001 0000
</pre>

<blockquote>
<p>这时候得到的结果，高一位为 1，当结果为 1 时，表示元素在扩容时位置发生了变化，新的下标位置等于原下标位置 + 原数组长度，如下图所示：</p>
</blockquote>
<p><img src="https://s1.ax1x.com/2020/07/20/Uf7E2q.png" alt=""></p>
<blockquote>
<p>其中红色的虚线图代表了扩容时元素移动的位置。</p>
</blockquote>
<hr>
<h2 id="2-HashMap-死循环分析"><a href="#2-HashMap-死循环分析" class="headerlink" title="2.HashMap 死循环分析"></a><strong>2.HashMap 死循环分析</strong></h2><hr>
<blockquote>
<p>以 JDK 1.7 为例，假设 HashMap 默认大小为 2，原本 HashMap 中有一个元素 key(5)，我们再使用两个线程：t1 添加元素 key(3)，t2 添加元素 key(7)，当元素 key(3) 和 key(7) 都添加到 HashMap 中之后，线程 t1 在执行到 Entry&lt;K,V&gt; next = e.next; 时，交出了 CPU 的使用权，源码如下：</p>
</blockquote>
<pre class="brush:java">
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next; // 线程一执行此处
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
</pre>

<blockquote>
<p>那么此时线程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) ；之后线程 t2 重新 rehash 之后链表的顺序被反转，链表的位置变成了 key(5) → key(7) → key(3)，其中 “→” 用来表示下一个元素。</p>
</blockquote>
<blockquote>
<p>当 t1 重新获得执行权之后，先执行 newTalbe[i] = e 把 key(3) 的 next 设置为 key(7)，而下次循环时查询到 key(7) 的 next 元素为 key(3)，于是就形成了 key(3) 和 key(7) 的循环引用，因此就导致了死循环的发生，如下图所示：</p>
</blockquote>
<p><img src="https://s1.ax1x.com/2020/07/20/Uf7Vx0.png" alt=""></p>
<blockquote>
<p>当然发生死循环的原因是 JDK 1.7 链表插入方式为首部倒序插入，这个问题在 JDK 1.8 得到了改善，变成了尾部正序插入。</p>
</blockquote>
<blockquote>
<p>有人曾经把这个问题反馈给了 Sun 公司，但 Sun 公司认为这不是一个问题，因为 HashMap 本身就是非线程安全的，如果要在多线程下，建议使用 ConcurrentHashMap 替代，但这个问题在面试中被问到的几率依然很大，所以在这里需要特别说明一下。</p>
</blockquote>
<hr>
<p><strong>小结</strong></p>
<blockquote>
<p>本文章介绍了 HashMap 的底层数据结构，在 JDK 1.7 时 HashMap 是由数组和链表组成的，而 JDK 1.8 则新增了红黑树结构，当链表长度达到 8 并且容器达到 64 时会转换为红黑树存储，以提升元素的操作性能。同时还介绍了 HashMap 的三个重要方法，查询、添加和扩容，以及 JDK 1.7 resize()  在并发环境下导致死循环的原因。</p>
</blockquote>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 jaytp@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">💰</a>
</p>






    




    </div>
    <div class="copyright">
        <p class="footer-entry">
    ©2016-2020 Yelog
</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<a class="" id="rocket" ></a>

    </div>
</div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>Help us with donation</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">alipay</label></span><span><label><input type="radio" name="pay" value="weixin">weixin</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.1.0" ></script>

<script src="/js/script.js?v=1.1.0" ></script>
<script>
    var img_resize = 'default';
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $("#post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>







</html>
